/*
 * Copyright (c) 2004-2006 The Regents of The University of Michigan
 * All rights reserved.
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions are
 * met: redistributions of source code must retain the above copyright
 * notice, this list of conditions and the following disclaimer;
 * redistributions in binary form must reproduce the above copyright
 * notice, this list of conditions and the following disclaimer in the
 * documentation and/or other materials provided with the distribution;
 * neither the name of the copyright holders nor the names of its
 * contributors may be used to endorse or promote products derived from
 * this software without specific prior written permission.
 *
 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
 * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
 * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
 * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 *
 * Authors: Gou Pengfei
 * Date:    Oct. 2011
 */
#include "base/intmath.hh"
#include "base/bitfield.hh"
#include "cpu/edge/pred/history_tracker.hh"
#include "cpu/base.hh"

template<class Impl>
HistoryTracker<Impl>::HistoryTracker(DerivEdgeCPUParams *params)
    : BasePredictor<Impl>(params),
      _name(params->name + ".HistoryTracker"),
      blockShiftAmt(params->blockShiftAmt)
{
    initVars();
}

template<class Impl>
HistoryTracker<Impl>::~HistoryTracker()
{
    DPRINTF(HistoryTracker,"HistoryTracker destructed!\n");
}

template<class Impl>
void
HistoryTracker<Impl>::initVars()
{
    for (int i = 0; i < Impl::MaxThreads; ++i) {
	globalExitHistory[i] = 0;
        globalTypeHistory[i] = 0;
        globalBinaryHistory[i] = 0;
        pathHistoryTable[i].resize(16, static_cast<Addr>(0));
    }

    for (int i = 0; i < Impl::MaxInFlightBlockNum; ++i) {
        checkpointEntries[i].pathHistory.resize(16, static_cast<Addr>(0));
    }

    typeIdBits = floorLog2(TheISA::NumBranchType);

    typeIdMask = (ULL(0x1) << typeIdBits) - 1;

    exitIdBits = floorLog2(TheISA::MaxExitsInBlock);

    exitIdMask = (ULL(0x1) << exitIdBits) - 1;

    DPRINTF(HistoryTracker, "HistoryTracker: exit id bits: %i"
            " exit id mask: %#x\n",
            exitIdBits, exitIdMask);

    DPRINTF(HistoryTracker, "HistoryTracker: type id bits: %i"
            " type id mask: %#x\n",
            typeIdBits, typeIdMask);
}

template<class Impl>
void
HistoryTracker<Impl>::reset()
{
    for (int i = 0; i < Impl::MaxThreads; ++i) {
	globalExitHistory[i] = 0;
        globalTypeHistory[i] = 0;
        globalBinaryHistory[i] = 0;

        for (int j = 0; j < pathHistoryTable[i].size(); ++j) {
            pathHistoryTable[i][j] = 0;
        }
    }
	
    for (int i = 0; i < Impl::MaxInFlightBlockNum; ++i) {
        checkpointEntries[i].reset();
    }
}

template<class Impl>
void
HistoryTracker<Impl>::lookup(Addr block_pc, BlockID block_id, ExitID pred_exit_id,
            BTypeID pred_type_id, uint64_t predication_pattern, ThreadID tid)
{
    uint64_t global_exit_history = globalExitHistory[tid];
    uint64_t global_type_history = globalTypeHistory[tid];
    uint64_t global_binary_history = globalBinaryHistory[tid];
    //uint64_t path_history = getPathHistory(tid);

    uint64_t index = block_id & (Impl::MaxInFlightBlockNum - 1); 

    DPRINTF(HistoryTracker, "HistoryTracker: Checkpoint current state to"
            " frame[%i]\n", index);

    // Checkpoint the current state.
    checkpointEntries[index].blockID = block_id;
    checkpointEntries[index].globalExitHistory = globalExitHistory[tid];
    checkpointEntries[index].globalTypeHistory = globalTypeHistory[tid];
    checkpointEntries[index].globalBinaryHistory = globalBinaryHistory[tid];
    checkpointEntries[index].pathHistory = pathHistoryTable[tid];
    checkpointEntries[index].predicationPattern = predication_pattern;

    // Speculatively update the global history
    globalExitHistory[tid] = ((global_exit_history << exitIdBits) |
            (pred_exit_id & exitIdMask));

    // Speculatively update the global history
    globalTypeHistory[tid] = ((global_type_history << typeIdBits) |
            (pred_type_id & typeIdMask));

    // Speculatively update the global history
    globalBinaryHistory[tid] = (pred_type_id != TheISA::seq) ?
        ((global_binary_history << 1) | ULL(0x1)) :
        (global_binary_history << 1);

    updatePathHistory(pathHistoryTable[tid], block_pc);

    DPRINTF(HistoryTracker, "Speculatively add exit id: %i,"
            " type: %i, binary: %i\n",
            pred_exit_id,
            pred_type_id,
            pred_type_id != TheISA::seq);
}

template<class Impl>
void
HistoryTracker<Impl>::update(Addr block_pc, BlockID block_id, ExitID actual_exit_id,
            BTypeID actual_type_id, ThreadID tid)
{
#ifndef NDEBUG
    assert(actual_exit_id >= 0 && actual_exit_id < TheISA::MaxExitsInBlock);
    assert(actual_type_id >= 0 && actual_type_id < TheISA::NumBranchType);

    uint64_t index = block_id & (Impl::MaxInFlightBlockNum - 1);

    DPRINTF(HistoryTracker, "HistoryTracker: Update from frame[%i]\n", index);

    assert(checkpointEntries[index].blockID == block_id);
#endif
}

template<class Impl>
void
HistoryTracker<Impl>::squash(Addr block_pc, BlockID block_id, ExitID actual_exit_id, 
            BTypeID actual_type_id, ThreadID tid)
{
    assert(actual_exit_id >= 0 && actual_exit_id < TheISA::MaxExitsInBlock);
    assert(actual_type_id >= 0 && actual_type_id < TheISA::NumBranchType);

    uint64_t index = block_id & (Impl::MaxInFlightBlockNum - 1) ;

    DPRINTF(HistoryTracker, "Squash from frame[%i] due to misprediction\n",
            index);

    assert(checkpointEntries[index].blockID == block_id);

    // Restore global history to state prior to this block.
    uint64_t global_exit_history = checkpointEntries[index].globalExitHistory;
    uint64_t global_type_history = checkpointEntries[index].globalTypeHistory;
    uint64_t global_binary_history = checkpointEntries[index].globalBinaryHistory;

    globalExitHistory[tid] = ((global_exit_history << exitIdBits) |
                         (actual_exit_id & exitIdMask));

    globalTypeHistory[tid] = ((global_type_history << typeIdBits) |
                         (actual_type_id & typeIdMask));

    globalBinaryHistory[tid] = (actual_type_id != TheISA::seq) ?
        ((global_binary_history << 1) | ULL(0x1)) : (global_binary_history << 1);

    PathHistory path = checkpointEntries[index].pathHistory;
    updatePathHistory(path, block_pc);
    pathHistoryTable[tid] = path;

    DPRINTF(HistoryTracker, "HistoryTracker: Squashing BP to Block [bid:%i].\n", 
            block_id);
}

template<class Impl>
void
HistoryTracker<Impl>::squash(BlockID block_id, ThreadID tid)
{
    uint64_t index = block_id & (Impl::MaxInFlightBlockNum - 1);

    DPRINTF(HistoryTracker, "Squash from frame[%i] due to fault\n",
            index);

    assert(checkpointEntries[index].blockID == block_id);

    globalExitHistory[tid] = checkpointEntries[index].globalExitHistory;
    globalTypeHistory[tid] = checkpointEntries[index].globalTypeHistory;
    globalBinaryHistory[tid] = checkpointEntries[index].globalBinaryHistory;
    pathHistoryTable[tid] = checkpointEntries[index].pathHistory;
}

template<class Impl>
void 
HistoryTracker<Impl>::updatePathHistory(PathHistory &path_history, Addr new_pc)
{
    DPRINTF(HistoryTracker, "Update path history,"
            " Pop: %#x; Push: %#x\n",
            path_history.back(),
            new_pc);

    path_history.pop_back();

    new_pc >>= blockShiftAmt;

    path_history.push_front(new_pc);
}

template<class Impl>
uint64_t
HistoryTracker<Impl>::getPathHistory(BlockID block_id, ThreadID tid)
{
    int index = block_id & (Impl::MaxInFlightBlockNum - 1);

    assert(checkpointEntries[index].blockID == block_id);

    PathHistory path = checkpointEntries[index].pathHistory;

    uint64_t path_hist = 0;

    for (int i = 0; i < path.size(); i++) {

        DPRINTF(HistoryTracker, "In frame[%i], path[%i]: %#x\n",
                index, i, path[i]);

        if (i < 16) {
            // Take 4 bits from each path address
            path_hist |= ((path[i] & ULL(0xF)) << (i * 4));
        }
    }

    return path_hist;
}

template<class Impl>
uint64_t
HistoryTracker<Impl>::getPathHistory(BlockID block_id, ThreadID tid, Addr pc)
{
    int index = block_id & (Impl::MaxInFlightBlockNum - 1);

    assert(checkpointEntries[index].blockID == block_id);

    PathHistory path = checkpointEntries[index].pathHistory;

    updatePathHistory(path, pc);

    uint64_t path_hist = 0;

    for (int i = 0; i < path.size(); i++) {

        DPRINTF(HistoryTracker, "In frame[%i], path[%i]: %#x\n",
                index, i, path[i]);

        if (i < 16) {
            // Take 4 bits from each path address
            path_hist |= ((path[i] & ULL(0xF)) << (i * 4));
        }
    }

    return path_hist;
}

template<class Impl>
uint64_t
HistoryTracker<Impl>::getExitHistory(BlockID block_id, ThreadID tid)
{
    int index = block_id & (Impl::MaxInFlightBlockNum - 1);

    assert(checkpointEntries[index].blockID == block_id);

    uint64_t hist = checkpointEntries[index].globalExitHistory;

    return hist;
}

template<class Impl>
uint64_t
HistoryTracker<Impl>::getExitHistory(BlockID block_id, ThreadID tid, ExitID exit_id)
{
    int index = block_id & (Impl::MaxInFlightBlockNum - 1);

    assert(checkpointEntries[index].blockID == block_id);

    uint64_t hist = checkpointEntries[index].globalExitHistory;

    hist = ((hist << exitIdBits) | (exit_id & exitIdMask));

    return hist;
}

template<class Impl>
uint64_t
HistoryTracker<Impl>::getTypeHistory(BlockID block_id, ThreadID tid)
{
    int index = block_id & (Impl::MaxInFlightBlockNum - 1);

    assert(checkpointEntries[index].blockID == block_id);

    uint64_t hist = checkpointEntries[index].globalTypeHistory;

    return hist;
}

template<class Impl>
uint64_t
HistoryTracker<Impl>::getTypeHistory(BlockID block_id, ThreadID tid, BTypeID type_id)
{
    int index = block_id & (Impl::MaxInFlightBlockNum - 1);

    assert(checkpointEntries[index].blockID == block_id);

    uint64_t hist = checkpointEntries[index].globalTypeHistory;

    hist = ((hist << typeIdBits) | (type_id & typeIdMask));

    return hist;
}

template<class Impl>
uint64_t
HistoryTracker<Impl>::getBinaryHistory(BlockID block_id, ThreadID tid)
{
    int index = block_id & (Impl::MaxInFlightBlockNum - 1);

    assert(checkpointEntries[index].blockID == block_id);

    uint64_t hist = checkpointEntries[index].globalBinaryHistory;

    return hist;
}

template<class Impl>
uint64_t
HistoryTracker<Impl>::getBinaryHistory(BlockID block_id, ThreadID tid, BTypeID type_id)
{
    int index = block_id & (Impl::MaxInFlightBlockNum - 1);

    assert(checkpointEntries[index].blockID == block_id);

    uint64_t hist = checkpointEntries[index].globalBinaryHistory;

    hist = (type_id != TheISA::seq) ? ((hist << 1) | ULL(0x1)) : (hist << 1);

    return hist;
}

template<class Impl>
uint64_t
HistoryTracker<Impl>::getPredicationPattern(BlockID block_id, ThreadID tid)
{
    int index = block_id & (Impl::MaxInFlightBlockNum - 1);

    assert(checkpointEntries[index].blockID == block_id);

    uint64_t pattern = checkpointEntries[index].predicationPattern;

    return pattern;
}

template<class Impl>
uint64_t
HistoryTracker<Impl>::getPathHistory(ThreadID tid)
{
    PathHistory path = pathHistoryTable[tid];

    uint64_t path_hist = 0;

    for (int i = 0; i < path.size(); i++) {
        if (i < 16) {
            // Take 4 bits from each path address
            path_hist |= ((path[i] & ULL(0xF)) << (i * 4));
        }
    }

    return path_hist;
}

